(define (max a b) (if (> a b) a b))
(define (pow n e)
  (if (= e 0)
      1
      (* n (pow n (- e 1)))))

(define (display-times s n)
  (if (> n 0)
      (begin (display s)
             (display-times s (- n 1)))
      #f))

(define (pad dm d left?)
  (let* ((floor (- dm d))
         (padding (- (pow 2 (+ floor (if left? 0 1))) 1)))
    (display-times " " padding)))

(define (node l v r) (lambda (q) (q l v r)))

(define (partition-levels q d q* out st empty?)
  (if (null? q)
      (if (if empty? #t (null? q*))
          (cons d (st '()))
          (let* ((result (out '())))
            (partition-levels q* (+ d 1) '() (lambda (x) x) (lambda (rest) (st (cons result rest))) #t)))
      (let* ((first (car q))
             (rest (cdr q)))
        (if first
            (first (lambda (l v r)
                     (let* ((out* (lambda (rest) (out (cons v rest)))))
                       (partition-levels rest d (append q* (cons l (cons r '()))) out* st #f))))
            (let* ((out* (lambda (rest) (out (cons "_" rest)))))
              (partition-levels rest d (append q* (cons #f (cons #f '()))) out* st empty?))))))

(define (print-levels st d dm)
  (if (< d dm)
      (begin
        (pad dm d #t)
        (display (car (car st)))
        (map (lambda (x)
               (pad dm d #f)
               (display x))
             (cdr (car st)))
        (newline)
        (print-levels (cdr st) (+ d 1) dm))
      #f))

(define t1
  (node (node (node (node #f 4 #f) 3 #f)
              2
              #f)
        1
        (node (node (node #f 6 #f) 6 #f)
              6
              (node #f 7 (node #f 8 #f)))))

(define t2 (partition-levels (cons t1 '()) 0 '() (lambda (x) x) (lambda (x) x) #t))
(define t3 (print-levels (cdr t2) 0 (car t2)))
